Interconnected networks include many router devices, such as gateways, to route high volumes of Internet traffic in the form of packets among many clients and the networks. The devices may each attempt to perform Deep Packet Inspection (DPI) on the packets transiting the device based on a set of DPI rules, which may include hundreds or even thousands of rules. Some of the DPI rules are complex and as a result require an appreciable amount of device resources, such as processing time and memory, when applied to any given packet. When device resource requirements are multiplied across many packets, many devices, and large sets of DPI rules, the requirements to implement DPI become onerous.